1. Field of the Invention
The present invention relates generally to a forward error correction (FEC) apparatus and method in a digital communication system, and in particular, to an apparatus and method for turbo decoding.
2. Description of the Related Art
In general, turbo codes are used for high-speed data communication, especially in Evolution Data Only (1×EV-DO) or Evolution Data and Voice (1×EV-DV). Berrou et. al. proposed the turbo codes in 1993. A turbo encoder is a parallel concatenation of two constituent Recursive Systematic Convolutional (RSC) encoders with a random interleaver in between. Thus, a turbo code is produced by encoding information bits and interleaved information bits in the RSC constituent encoders. Turbo decoding involves a serial concatenation of two constituent decoders, each for decoding iteratively, exchanging its extrinsic information with the other constituent decoder. There are three algorithms applicable for each constituent decoder: Log-MAP, Max-Log-MAP, and Soft Output Viterbi Algorithm (SOVA).
The Log-MAP algorithm is the log-domain implementation of a MAP algorithm which is optimal for decoding an information word in a trellis. The Max-Log-MAP algorithm is easily derived from the Log-MAP algorithm by an approximation of metric computation. Despite the advantage of simple implementation as compared to the Log-MAP algorithm, the Max-Log-MAP algorithm leads to performance degradation when perfect Signal-to-Noise Ratio (SNR) is possible at a receiver.
For the Log-MAP algorithm, state metrics and an Log Likelihood Ratio (LLR) are computed. State metrics α and β for a state (s and s′) in a trellis at decoding time k are in a recursive relation expressed as
                                          log            ⁡                          (                                                α                  k                                ⁡                                  (                  s                  )                                            )                                =                      log            (                                          ∑                s                            ⁢                                                                    α                                          k                      -                      1                                                        ⁡                                      (                                          s                      ′                                        )                                                  ⁢                                                      γ                    k                                    ⁡                                      (                                                                  s                        ′                                            ,                      s                                        )                                                                        )                          ,                                  ⁢                              log            ⁡                          (                                                β                                      k                    -                    1                                                  ⁡                                  (                                      s                    ′                                    )                                            )                                =                      log            (                                          ∑                s                            ⁢                                                                    β                    k                                    ⁡                                      (                    s                    )                                                  ⁢                                                      γ                    k                                    ⁡                                      (                                                                  s                        ′                                            ,                      s                                        )                                                                        )                                              (        1        )            where γ is a branch metric defined by a symbol received on a channel. Using the state metrics and the branch metric, the LLR of a kth symbol is obtained by
                                                                                          L                  ⁡                                      (                                                                  u                        ^                                            k                                        )                                                  =                                  log                  ⁡                                      (                                                                                            ∑                                                                                    (                                                                                                s                                  ′                                                                ,                                s                                                            )                                                        ,                                                                                          u                                k                                                            =                              0                                                                                                      ⁢                                                                                                            α                                                              k                                -                                1                                                                                      ⁡                                                          (                                                              s                                ′                                                            )                                                                                ⁢                                                                                    γ                              k                                                        ⁡                                                          (                                                                                                s                                  ′                                                                ,                                s                                                            )                                                                                ⁢                                                                                    β                              k                                                        ⁡                                                          (                              s                              )                                                                                                                                                                            ∑                                                                                    (                                                                                                s                                  ′                                                                ,                                s                                                            )                                                        ,                                                                                          u                                k                                                            =                              1                                                                                                      ⁢                                                                                                            α                                                              k                                -                                1                                                                                      ⁡                                                          (                                                              s                                ′                                                            )                                                                                ⁢                                                                                    γ                              k                                                        ⁡                                                          (                                                                                                s                                  ′                                                                ,                                s                                                            )                                                                                ⁢                                                                                    β                              k                                                        ⁡                                                          (                              s                              )                                                                                                                                            )                                                                                                                          =                                  log                  ⁡                                      (                                                                                            ∑                          i                                                ⁢                                                  ⅇ                                                                                    M                              0                                                        ⁡                                                          (                              i                              )                                                                                                                                                                            ∑                          i                                                ⁢                                                  ⅇ                                                                                    M                              1                                                        ⁡                                                          (                              i                              )                                                                                                                                            )                                                                                                                          =                                                                            M                      0                                        ⁡                                          (                      0                      )                                                        -                                                            M                      1                                        ⁡                                          (                      0                      )                                                        +                                      f                    c                                                                                      ⁢                                  ⁢        where        ,                                  ⁢                              f            c                    =                                    log              (                              1                +                                                      ∑                                          i                      ≠                      0                                                        ⁢                                      ⅇ                                          -                                              (                                                                                                            M                              0                                                        ⁡                                                          (                              0                              )                                                                                -                                                                                    M                              0                                                        ⁡                                                          (                              i                              )                                                                                                      )                                                                                                        )                        -                          log              (                              1                +                                                      ∑                                          i                      ≠                      0                                                        ⁢                                      ⅇ                                          -                                              (                                                                                                            M                              1                                                        ⁡                                                          (                              0                              )                                                                                -                                                                                    M                              1                                                        ⁡                                                          (                              i                              )                                                                                                      )                                                                                                        )                                                          (        2        )            
In Eq. (2), Mn(i) is an ith metric in a descending-order arrangement of metrics (log(αk−1(s′)γk(s′,s)βk(s))) for an information symbol n (0 or 1) in the state set (s, s′) at time k. Therefore, M0(0) and M1(0) are the best metrics for the information symbol 1 and 0 at time k, and fc is a correction value defined by the difference between the best metric and the other metrics for each information symbol. Accordingly, the LLR is updated using the best metric difference between the information symbols 0 and 1 at time k and the correction value fc.
In summary, the Log-MAP algorithm generates all state metrics in a trellis for each constituent decoder by Eq. (1) and computes the LLR of a code symbol in the trellis using its state metrics by Eq. (2). Each constituent decoder feeds extrinsic information derived from the LLR to the other constituent decoder, for iterative decoding. In this manner, turbo decoding is performed.
The Max-Log-MAP algorithm is a simplified version of the Log-MAP algorithm by reducing the state metric computation of Eq. (1) to a maximum operation expressed as
                                          log            ⁢                                                  ⁢                                          α                k                            ⁡                              (                s                )                                              ≈                                    max                              s                ′                                      ⁢                          (                              log                ⁡                                  (                                                                                    α                                                  k                          -                          1                                                                    ⁡                                              (                                                  s                          ′                                                )                                                              ⁢                                                                  γ                        k                                            ⁡                                              (                                                                              s                            ′                                                    ,                          s                                                )                                                                              )                                            )                                      ⁢                                  ⁢                              log            ⁢                                                  ⁢                                          β                                  k                  -                  1                                            ⁡                              (                                  s                  ′                                )                                              ≈                                    max              s                        ⁢                          (                              log                ⁡                                  (                                                                                    β                        k                                            ⁡                                              (                        s                        )                                                              ⁢                                                                  γ                        k                                            ⁡                                              (                                                                              s                            ′                                                    ,                          s                                                )                                                                              )                                            )                                                          (        3        )            
In the same manner, the LLR of the kth decoding symbol is simply computed by the maximum operation. The LLR is updated using only the best metric difference, assuming fc to be 0. Thus,L({circumflex over (u)}k)=M0(0)−M1(0)  (4)
In summary, the Max-Log-MAP algorithm searches all state metrics in the trellis for each constituent decoder by the maximum operation of Eq. (3) and computes the LLR of a code symbol in the trellis using the best metric difference between information symbols 0 and 1 by Eq. (4). Extrinsic information derived from the LLR is fed to the other constituent decoder, for iterative decoding. In this manner, turbo decoding is performed.
A so-called Max-Log-MAP algorithm with Feedback Gain (FG) considers an additional gain derived from the LLR computed by Eq. (4) to improve the decoding performance of the Max-Log-MAP algorithm. A weighting factor multiplied as the feedback gain is about 0.588235 and applied only to extrinsic information from a second constituent decoder.
Since the Log-MAP algorithm is the log-domain implementation of an optimum symbol by symbol MAP decoding algorithm, it performs as well as the MAP algorithm. However, when the Log-MAP algorithm is implemented in hardware, the function of log(1+e−Δ) defining each metric must be implemented in hardware or in the form of a look-up table. The Max-Log-MAP algorithm, on the other hand, requires no look-up table, but performs worse than the Log-MAP algorithm. The benefits and shortcomings of the Log-MAP algorithm and the Max-Log-MAP algorithm are as follows.
(1) The Log-MAP algorithm: Since it is an optimum symbol by symbol decision algorithm, it is the best turbo decoding algorithm. However, the implementation of log(1+e−Δ) increases hardware complexity. Moreover, log(1+e−Δ) is a non-linear function and thus an accurate SNR estimate of a received symbol is required to compute branch metrics by which Δ is defined. If the SNR estimation involves errors, this SNR mismatch degrades performance markedly.
(2) The Max-Log-MAP algorithm: Log( ) computation is not required for metric calculation because all metrics are calculated by the maximum operation. Therefore, the problem of increased hardware complexity as encountered in the Log-MAP algorithm is not produced. Furthermore, the calculation of metrics by the maximum operation obviates the need of the non-linear function log(1+e−Δ), which implies that there are no SNR mismatch-related problems. However, since the Max-Log-MAP algorithm is an approximation of the Log-MAP algorithm, it performs about 0.3 to 0.4 dB worse than the Log-MAP algorithm.
As described above, the Log-MAP algorithm and the Max-Log-MAP algorithm cause increased hardware complexity and performance degradation as their respective shortcomings.